tail recursion modulo cons

A generalisation of {tail recursion}

introduced by D.H.D. Warren. It applies when the last thing a

function does is to apply a constructor functions (e.g. cons)

to an application of a non-primitive function. This is

transformed into a tail call to the function which is also

passed a pointer to where its result should be written. E.g.

f [] ◦ []

f (x:xs) ◦ 1 : f xs

is transformed into (pseudo {C}/{Haskell}):

f [] ◦ []

f l ◦ f' l allocate_cons

f' [] p ◦ { ▫p ◦ nil;

return ▫p

}

f' (x:xs) p ◦ { cell ◦ allocate_cons;

▫p ◦ cell;

cell.head ◦ 1;

return f' xs &cell.tail

}

where allocate_cons returns the address of a new cons cell, ▫p

is the location pointed to by p and &c is the address of c.

[D.H.D. Warren, DAI Research Report 141, University of

Edinburgh 1980].

(1995-03-06)